<HTML>
<BODY>
Matrix <i>interfaces and factories</i>; efficient and flexible dense and sparse 
1, 2, 3 and d-dimensional matrices holding objects or primitive data types such 
as <tt>int</tt>, <tt>double</tt>, etc; Templated, fixed sized (not dynamically 
resizable); Also known as <i>multi-dimensional arrays</i> or<i> Data Cubes</i>. 
Note that d-dimensional and <tt>int</tt> based matrices are not yet provided. 
<p></p>
<h1><a name="Overview"></a>Getting Started</h1>
<ol>
  <li><a href="#Overview">Overview</a></li>
  <li><a href="#Introduction">Introduction</a> </li>
  <li><a href="#SemanticsOfViews">Semantics of Views</a></li>
  <li><a href="#FunctionObjects">Functional Programming with Objects</a></li>
  <li><a href="#Algorithms">Algorithms</a></li>
  <li><a href="#LinearAlgebra">Linear Algebra</a></li>
  <li><a href="#Orthogonality">Orthogonality and Polymorphism</a></li>
  <li><a href="#PackageOrganization">Package Organization, Naming Conventions, 
    Policies</a></li>
  <li><a href="#Performance">Performance</a></li>
  <li><a href="#Notes">Notes</a> </li>
</ol>
<h2></h2>
<h2>1. Overview</h2>
<p>The matrix package offers flexible object oriented abstractions modelling multi-dimensional 
  arrays, resembling the way they can be manipulated in Fortran. It is designed 
  to be scalable, not only in terms of performance and memory requirements, but 
  also in terms of the number of operations that make sense on such data structures. 
  Features include</p>
<table width="75%" border="0" bgcolor="#EEEEEE">
  <tr valign="top" align="left"> 
    <td> 
      <table border="0" cellpadding="0" cellspacing="0" width="358">
        <tr> 
          <td colspan="2" bgcolor="#770000"> 
            <p align="CENTER"><font color="#FFFFFF"><b>Multi-dimensional Array 
              Types</b></font> 
          </td>
        </tr>
        <tr valign="top"> 
          <td align="LEFT" width="180"> 
            <ul>
              <li>dense 
              <li>sparse hashed 
              <li>sparse row compressed
            </ul>
          </td>
          <td align="LEFT" width="180"> 
            <ul>
              <li>1-d, 2-d, 3-d
            </ul>
          </td>
        </tr>
      </table>
    </td>
    <td> 
      <table border="0" cellpadding="0" cellspacing="0" width="358">
        <tr> 
          <td colspan="2" bgcolor="#770000"> 
            <p align="CENTER"><font color="#FFFFFF"><b>Matrix Operations</b></font> 
          </td>
        </tr>
        <tr valign="top"> 
          <td align="LEFT" width="180"> 
            <ul>
              <li>matrix-matrix multiply 
              <li>matrix-vector multiply 
              <li>inner, outer products 
              <li>tranposition 
            </ul>
          </td>
          <td align="LEFT" width="180"> 
            <ul>
              <li>equation solving 
              <li>permutation (pivoting)
              <li>integer powers 
              <li>norms 
              <li>trace 
            </ul>
          </td>
        </tr>
      </table>
    </td>
  </tr>
  <tr valign="top" align="left"> 
    <td> 
      <table border="0" cellpadding="0" cellspacing="0" width="358">
        <tr> 
          <td colspan="2" bgcolor="#770000"> 
            <p align="CENTER"><font color="#FFFFFF"><b>Array Views (by Reference)</b></font> 
          </td>
        </tr>
        <tr valign="top"> 
          <td align="LEFT" width="180"> 
            <ul>
              <li>sub-range 
              <li>slice 
              <li>dice 
              <li>flip 
              <li>stride 
            </ul>
          </td>
          <td align="LEFT" width="180"> 
            <ul>
              <li>selection 
              <li>sort 
            </ul>
            <ul>
              <li>assigment 
              <li>copying 
            </ul>
          </td>
        </tr>
      </table>
    </td>
    <td> 
      <table border="0" cellpadding="0" cellspacing="0" width="358">
        <tr> 
          <td valign="MIDDLE" colspan="2" bgcolor="#770000"> 
            <p align="CENTER"><font color="#FFFFFF"><b>Matrix Factorizations and 
              Decompositions</b></font> 
          </td>
        </tr>
        <tr valign="top"> 
          <td width="180" align="LEFT"> 
            <ul>
              <li>LU 
              <li>QR 
              <li>Cholesky 
              <li>eigenvectors and eigenvalues 
              <li>singular value (SVD) 
            </ul>
          </td>
          <td align="LEFT" width="180"> 
            <ul>
              <li> inverse 
              <li>pseudoinverse 
              <li>condition 
              <li>determinant 
              <li>rank 
            </ul>
          </td>
        </tr>
      </table>
    </td>
  </tr>
  <tr valign="top" align="left"> 
    <td> 
      <table border="0" cellpadding="0" cellspacing="0" width="358">
        <tr> 
          <td colspan="2" bgcolor="#770000"> 
            <p align="CENTER"><font color="#FFFFFF"><b>Elementwise Array Operations</b></font> 
          </td>
        </tr>
        <tr valign="top"> 
          <td align="LEFT" width="180"> 
            <ul>
              <li>addition 
              <li>subtraction 
              <li>multiplication 
              <li>division 
              <li>power 
              <li>square root 
              <li>logarithm 
              <li>exponential 
              <li>absolute value 
              <li>trigonometric functions 
            </ul>
          </td>
          <td align="LEFT" width="180"> 
            <ul>
              <li> assignment 
              <li>functional programming via user-defined functions (for transformations, 
                aggregations, selections, sorting) 
              <li>comparison 
            </ul>
          </td>
        </tr>
      </table>
      <p>&nbsp;</p>
    </td>
    <td> 
      <table border="0" cellpadding="0" cellspacing="0" width="358" height="55">
        <tr> 
          <td valign="MIDDLE" colspan="2" bgcolor="#770000"> 
            <p align="CENTER"><font color="#FFFFFF"><b>Columnwise Data Analysis</b></font> 
          </td>
        </tr>
        <tr valign="top"> 
          <td width="180" align="LEFT"> 
            <ul>
              <li>covariance, correlation matrix 
              <li>maximum 
              <li>minimum 
              <li>mean 
              <li>variance, standard deviation 
              <li>median 
              <li>exact and approximate quantiles 
            </ul>
          </td>
          <td align="LEFT" width="180"> 
            <ul>
              <li>(cumulative) sum 
              <li>(cumulative) product 
              <li>harmonic, geometric mean 
              <li>skew, kurtosis 
              <li>moments 
              <li>frequencies 
              <li>sorting 
            </ul>
          </td>
        </tr>
      </table>
    </td>
  </tr>
  <tr valign="top" align="left"> 
    <td> 
      <table border="0" cellpadding="0" cellspacing="0" width="358">
        <tr> 
          <td colspan="2" bgcolor="#770000"> 
            <p align="CENTER"><font color="#FFFFFF"><b>Array and Matrix Utilities</b></font> 
          </td>
        </tr>
        <tr valign="top"> 
          <td align="LEFT" width="180"> 
            <ul>
              <li> dense and sparse creation 
              <li>string formatting 
              <li>up-down or left-right concatenation 
              <li>create, extract block matrix 
            </ul>
          </td>
          <td align="LEFT" width="180"> 
            <ul>
              <li>create, extract diagonals 
              <li>extract upper, lower triangular parts 
              <li>random matrix, array 
            </ul>
          </td>
        </tr>
      </table>
    </td>
    <td> 
      <p>&nbsp;</p>
    </td>
  </tr>
</table>
<p>File-based I/O can be achieved through the standard Java-built-in serialization 
  mechanism. All classes implement the {@link java.io.Serializable} interface. 
  However, the toolkit is entirely decoupled from advanced I/O and visualisation 
  techniques. It provides data structures and algorithms only. </p>
<p> This toolkit borrows many fundamental concepts and terminology from the IBM 
  <a href="http://math.nist.gov/javanumerics/array/"> Array</a> package written 
  by Jose Moreira, Marc Snir and Sam Midkiff. They introduced well designed multi-dimensional 
  arrays to the Java world. 
<p><a href="#Overview">Back</a> to Overview
<h2><a name="Introduction"></a>2. Introduction</h2>
<p>Multi-dimensional arrays are arguably <i>the</i> most frequently used abstraction 
  in scientific and technical codes. They support a broad variety of applications 
  in the domain of Physics, Linear Algebra, Computational Fluid Dynamics, Relational 
  Algebra, Statistics, Graphics Rendering and others. For example many physics 
  problems can be mapped to matrix problems: Linear and nonlinear systems of equations, 
  linear differential equations, quantum mechanical eigenvalue problems, Tensors, 
  etc. Physics<i> NTuples</i> are essentially 2-d arrays. In the area of Online 
  Analytic Processing <i>(OLAP</i>) multi-dimensional arrays are called <i>Data 
  Cubes</i>. In this toolkit they are called <i>Matrices</i>, simply because the 
  term <i>Array</i> is already heavily overloaded and <i>Data Cube</i> is somewhat 
  fuzzy to many people.</p>
<h2></h2>
<p>Matrices are basically rectangular grids with each cell in the grid containing 
  a single value. Cells are accessed via zero-based integer indexes. Matrices 
  can be characterized by</p>
<ul>
  <li> <i>Rank</i>: The number of dimensions (axes). Most frequently used are one and 
    two dimensions.</li>
  <li> <i>Shape:</i> Each dimension has a certain number of slots. All slots together 
    make up the shape. For example, a 2-dimensional 10 x 50 matrix has 10 slots 
    along its first dimension, and 50 slots along its second dimension, yielding 
    500 cells.</li>
  <li><i>Value type</i>: The type of value to be stored in each cell. Can be integer, 
    floating point or an arbitrary object.</li>
</ul>
<p>Here is an example of a <tt>8x8x8</tt> matrix and other matrices. 
<p><img src="doc-files/slice.gif" width="644" height="401"> 
<p>As broad as the spectrum of applications using multi-dimensional matrices is 
  the number of operations meaningful on them. Only a smallish subset of those 
  operations are provided in this library. We hope that this will change over 
  time. However, core multi-purpose functionality such as <i>subrange</i>, <i>slice</i>, 
  <i>dice</i>, <i>flip</i>, <i>stride</i>, <i>selection</i> and<i> sort</i> views 
  as well as <i>copying</i> and <i>numerical transformations</i> (*,/,+,-,...) 
  are efficiently provided. The primary motivation for views is ease-of-use. Views 
  allow to express otherwise complex aggregate operations in simple terms. They 
  seek to present a matrix in different ways to a user and/or functions operating 
  on a matrix. Subranging, slicing, dicing, flipping, striding, selecting and 
  sorting are virtual transformations: they merely alter the way we see the <i>same 
  data</i>. They produce <i>views</i>, which are objects that know only about 
  certain regions of the entire matrix. Views all point to the same data, so changes 
  in the view are reflected in the original matrix, all other possibly nested 
  views of the original matrix, and vice-versa. Pete and Jane can look at a flower 
  in many different ways although it remains one single flower. If Pete steps 
  on top of the flower, Jane will certainly note. Which is not the case when copying 
  is applied, since it is a materializing transformation. It means, the connection 
  between the original and the copy is lost. If Pete is stepping on top of a rose 
  and Jane is admiring another one, it won't have any impact on her. Views can 
  arbitrarily be nested. They eliminate the need for explicit region operations. 
  Any operation on a matrix can be used as a region restricted operation by operating 
  on a matrix view instead of the whole matrix. Here are some examples: 
<p>&nbsp; 
<table border="0">
  <tr> 
    <td>Lets construct a dense 3 x 4 matrix</td>
    <td nowrap>&nbsp;</td>
  </tr>
  <tr> 
    <td> 
      <p><tt>DoubleMatrix2D matrix;<br>
        matrix </tt><tt>= new DenseDoubleMatrix2D(3,4);<br>
        </tt><tt>//matrix </tt><tt>= new SparseDoubleMatrix2D(3,4);</tt><tt> </tt><tt>// 
        has same interface<br>
        </tt><tt>//matrix </tt><tt>= new RCDoubleMatrix2D(3,4);</tt><tt> </tt><tt> 
        // has same interface<br>
        </tt><tt></tt><tt>System.out.println(matrix); </tt></p>
    </td>
    <td nowrap><tt>3 x 4 matrix: <br>
      0 0 0 0 <br>
      0 0 0 0 <br>
      0 0 0 0 </tt></td>
  </tr>
  <tr> 
    <td> We can get rid of the typed distinction between sparse and dense matrices. 
      Use a factory, as follows</td>
    <td nowrap>&nbsp;</td>
  </tr>
  <tr> 
    <td> 
      <p><tt>DoubleFactory2D factory;<br>
        if (wantDense) factory = DoubleFactory2D.dense;<br>
        else if (wantSparseHashed)&nbsp;factory = DoubleFactory2D.sparse;<br>
        else factory = DoubleFactory2D.rowCompressed;<br>
        <br>
        // From now on all instantiations will go via the factory -<br>
        // No explicit constructor calls anymore</tt><tt><br>
        DoubleMatrix2D matrix = factory.make(3,4);<br>
        System.out.println(matrix);</tt> </p>
      </td>
    <td nowrap><tt>3 x 4 matrix: <br>
      0 0 0 0 <br>
      0 0 0 0 <br>
      0 0 0 0 </tt></td>
  </tr>
  <tr> 
    <td>The shape can be retrieved with <br>
      <tt>int rows = matrix.rows(); <br>
      int columns = matrix.columns();</tt> </td>
    <td nowrap>&nbsp;</td>
  </tr>
  <tr> 
    <td>We set and get a cell value:</td>
    <td nowrap>&nbsp;</td>
  </tr>
  <tr> 
    <td> 
      <p><tt>int row = 2, column = 0;<br>
        </tt><tt>matrix.set(row,column, 7);<br>
        System.out.println(matrix.get(row,column));<br>
        // --&gt; 7</tt></p>
    </td>
    <td nowrap><tt>3 x 4 matrix <br>
      0 0 0 0 <br>
      0 0 0 0 <br>
      7 0 0 0 </tt></td>
  </tr>
  <tr> 
    <td>Looping is done as expected:</td>
    <td nowrap>&nbsp;</td>
  </tr>
  <tr> 
    <td> <tt> 
      <pre>
double sum = 0;
for (int row=rows; --row &gt;= 0; ) {
   for (int column=columns; --column &gt;= 0; ) {
      sum += matrix.get(row,column); // bounds check
      //sum += matrix.getQuick(row,column); // no bounds check
   }
}
System.out.println(sum); 
</pre>
      </tt> </td>
    <td nowrap>&nbsp;</td>
  </tr>
  <tr> 
    <td>The following idiom uses a subranging view to set all cells of the box 
      <br>
      starting at <tt>[1,0]</tt> with width and height of 2 to the value <tt>1</tt>: 
    </td>
    <td nowrap>&nbsp;</td>
  </tr>
  <tr> 
    <td><tt>matrix.viewPart(1,0,2,2).assign(1);<br>
      System.out.println(matrix); <br>
      </tt></td>
    <td nowrap><tt>3 x 4 matrix <br>
      0 0 0 0 <br>
      1 1 0 0 <br>
      1 1 0 0 </tt></td>
  </tr>
  <tr> 
    <td> 
      <p>A dicing view can be used to print the matrix in a different format (4 
        x 3). This is equivalent to a zero-copy transposition:</p>
    </td>
    <td nowrap>&nbsp;</td>
  </tr>
  <tr> 
    <td><tt>System.out.println(matrix.viewDice())</tt></td>
    <td nowrap><tt>4 x 3 matrix <br>
      0 1 1 <br>
      0 1 1 <br>
      0 0 0 <br>
      0 0 0 </tt></td>
  </tr>
  <tr> 
    <td> 
      <p>Next, a flipping view mirrors the matrix. </p>
    </td>
    <td nowrap>&nbsp;</td>
  </tr>
  <tr> 
    <td><tt>System.out.println(matrix.viewColumnFlip());</tt></td>
    <td nowrap><tt>3 x 4 matrix <br>
      0 0 0 0 <br>
      0 0 1 1 <br>
      0 0 1 1 </tt></td>
  </tr>
  <tr> 
    <td> 
      <p>A slicing view shows the second row, a 1-dimensional matrix:</p>
    </td>
    <td nowrap>&nbsp;</td>
  </tr>
  <tr> 
    <td><tt>System.out.println(matrix.viewRow(1)); </tt></td>
    <td nowrap><tt>4 matrix <br>
      1 1 0 0 </tt></td>
  </tr>
  <tr> 
    <td> 
      <p>Note that the result of a slicing operation is not a 2-d matrix with 
        one row, but a true 1-d <b>type</b> with all capabilities of the type, 
        namely {@link cern.colt.matrix.DoubleMatrix1D}, generated in constant 
        time.</p>
      <p>The slicing view is now fed into some external algorithm expecting a 
        1-dimensional matrix:<br>
        <tt>someAlgorithm(matrix.viewRow(1));</tt> </p>
    </td>
    <td nowrap>&nbsp;</td>
  </tr>
  <tr> 
    <td>If the algorithm is designed such that it modifies data of the row, <br>
      but we want to avoid any side-effects, we can feed it a copy of the row: 
      <tt><br>
      someAlgorithm(matrix.viewRow(1).copy());</tt> </td>
    <td nowrap>&nbsp;</td>
  </tr>
  <tr> 
    <td>A stride view shows every row and every second column. It is useful for 
      scatter/gather operations.</td>
    <td nowrap>&nbsp;</td>
  </tr>
  <tr> 
    <td><tt>System.out.println(matrix.viewStrides(1,2)); </tt></td>
    <td nowrap><tt>3 x 2 matrix <br>
      0 0<br>
      1 0<br>
      1 0</tt></td>
  </tr>
  <tr> 
    <td>A selection view shows explicitly specified rows and columns. Imagine 
      a 2-d matrix. Columns are attributes <i>energy</i>, <i>tracks</i>, <i>momentum</i>, 
      the rows hold <tt>N</tt> such measurements, as recorded by some device. 
      We want to operate on some subset of the columns and exclude some measurements 
      not of interest for our analysis.</td>
    <td nowrap>&nbsp;</td>
  </tr>
  <tr> 
    <td><tt>int[] rowIndexes = {0,2};<br>
      int[] columnIndexes = {2,3,1,1};<br>
      System.out.println(matrix.viewSelection(rowIndexes,columnIndexes)); </tt></td>
    <td nowrap><tt>2 x 4 matrix <br>
      0 0 0 0 <br>
      0 0 1 1 </tt></td>
  </tr>
  <tr> 
    <td>A sort view with row flipping shows rows sorted descending by column 1:</td>
    <td nowrap>&nbsp;</td>
  </tr>
  <tr> 
    <td><tt>System.out.println(matrix.viewSorted(1).viewRowFlip()); </tt></td>
    <td nowrap><tt>3 x 4 matrix <br>
      1 1 0 0 <br>
      1 1 0 0 <br>
      0 0 0 0 </tt></td>
  </tr>
  <tr> 
    <td>Last, lets combine some of the methods to stimulate imagination:</td>
    <td nowrap>&nbsp;</td>
  </tr>
  <tr> 
    <td><tt>matrix.viewPart(0,1,2,2).viewRowFlip().viewColumn(0).assign(2);<br>
      System.out.println(matrix); <br>
      </tt></td>
    <td nowrap><tt>3 x 4 matrix <br>
      0 2 0 0 <br>
      1 2 0 0 <br>
      1 1 0 0 </tt></td>
  </tr>
</table>
<p><a href="#Overview">Back</a> to Overview 
<h2></h2>
<h2><a name="SemanticsOfViews"></a>3. Semantics of Views </h2>
<p>Find out more about the <a href="doc-files/semanticsOfViews.html">precise semantics</a> 
  of views and basic operations.</p>
<p><a href="#Overview">Back</a> to Overview
<h2></h2>
<h2><a name="Orthogonality"></a>4. Orthogonality and Polymorphism</h2>
<p>If this section sounds trivial and obvious, you can safely skip it.<br>
  The desire for orthogonality is a desire for &quot;plug and play&quot;. Orthogonality 
  demands that everything can be plugged together with everything, or, in other 
  words, that different things can be handled in the same way. Of course only 
  things that syntactically and semantically share a common set of interfaces 
  can be handled in the same way, or work together in the same way. Polymorphism 
  is an implementation mechanism supporting orthogonality. It is about being able 
  to exchange things without noticing any difference. Again, as long as the things 
  adhere to some common interface.</p>
<p>The common interface for matrices is defined in abstract base classes (e.g. 
  {@link cern.colt.matrix.DoubleMatrix2D}). Note that looking at the documentation 
  of some concrete instantiable class (e.g. {@link cern.colt.matrix.impl.DenseDoubleMatrix2D}, 
  {@link cern.colt.matrix.impl.SparseDoubleMatrix2D}, {@link cern.colt.matrix.impl.RCDoubleMatrix2D}<img src="../doc-files/new.gif" width="32" height="22" align="top">) 
  will not reveal more information than can be obtained by looking at the abstract 
  base classes. The convention is that concrete classes <i>do no subsetting or 
  supersetting</i>. They override methods to implement behaviour dictated by abstract 
  classes, or to improve performance, but they do not introduce any new functionality. 
</p>
<p>Although each matrix of a given rank and value type comes with dense and sparse 
  implementations and a multitude of views, there is from the user interface perspective 
  no difference between them. All implementations have exactly the same interface 
  with exactly the same semantics attached. In particular, everything that &quot;can 
  be done&quot; with a dense matrix can also be done with a sparse specie, and 
  vice-versa. The same principle applies to views. </p>
<p><i>This implies that any internal or external function expecting as argument 
  an abstract matrix (and any operation defined on an abstract matrix) can be 
  used with any kind of matrix of the given rank and value type, whether it be 
  dense, sparse, sub-ranged, selected, strided, sorted, flipped, transposed, or 
  any arbitrary combination thereof. For example, dense matrices can be multiplied/assigned/transformed/compared 
  with sparse matrices, dense stride views with dense flip views, dense sorted 
  flipped sub-range views with sparse selection views, in all conceivable permutations. 
  The result is a powerful and flexible tool.</i></p>
<h2></h2>
<p><a href="#Overview">Back</a> to Overview 
<h2><a name="FunctionObjects"></a>5. Function Objects</h2>
<p>Function objects conveniently allow to express arbitrary functions in a generic 
  manner. Essentially, a function object is an object that can perform a function 
  on some arguments. It has a minimal interface: a method <tt>apply</tt> that 
  takes the arguments, computes something and returns some result value. Function 
  objects are comparable to function pointers in C used for call-backs. Here are 
  some examples demonstrating how function objects can be used to </p>
<ol>
  <li> <a href="doc-files/function1.html">transform</a> a matrix A into another 
    matrix B which is a function of the original matrix A (and optionally yet 
    another matrix C)</li>
  <li> <a href="doc-files/function2.html">aggregate</a> cell values or a function 
    of them</li>
  <li> <a href="doc-files/function3.html">generate selection views</a> for cells 
    satisfying a given condition</li>
  <li> <a href="doc-files/function4.html">sort</a> matrix rows or columns into 
    a user specified order</li>
  <li>You will most likely use them to do many more powerful things </li>
</ol>
<p>Usually, assign operations are heavily optimized for frequently used function 
  objects like plus, minus, mult, div, plusMult, minusMult, etc. Concerning the 
  performance of unoptimized function objects, see {@link cern.jet.math.Functions}.</p>
<p></p>
<p><a href="#Overview">Back</a> to Overview
<h2></h2>
<h2><a name="Algorithms"></a>6. Algorithms </h2>
<p>As already stated, the spectrum of applications using multi-dimensional matrices 
  is large and so is the number of operations meaningful on them. One single flat 
  interface cannot satisfy all needs and would soon get unmanageably fat. To avoid 
  interface bloat, it can be a good idea to separate algorithms from data structures. 
  Special purpose algorithms, wrappers, mediators etc. should therefore go into 
  external packages and classes. By using the common interfaces defined in abstract 
  classes, algorithms can be implemented such that they generically work both 
  on sparse and dense matrices and all their views. This will ensure scalability 
  over time, as more and more features are added. </p>
<p>Some algorithms for formatting, sorting, statistics and partitioning, are, 
  for example, provided in the package {@link cern.colt.matrix.doublealgo}. </p>
<p><a href="#Overview">Back</a> to Overview</p>
<h2></h2>
<h2><a name="LinearAlgebra"></a>7. Linear Algebra</h2>
<p>See the documentation of the linear algebra package {@link cern.colt.matrix.linalg}.</p>
<p><a href="#Overview">Back</a> to Overview </p>
<h2><a name="PackageOrganization"></a>8. Package Organization, Naming Conventions, 
  Policies</h2>
<h4>Class Naming / Inheritance</h4>
<p>Have a look at the javadoc <a href="package-tree.html">tree view</a> to get 
  the broad picture. The classes for matrices of a given rank are derived from 
  a common abstract base class named <tt>&lt;ValueType&gt;Matrix&lt;Rank&gt;D</tt>, 
  which is in many ways equivalent to an &quot;interface&quot;. <b>99% of the 
  time you will operate on these abstract classes only</b>. For example, all 2-dimensional 
  matrices operating on <tt>double</tt> values are derived from {@link cern.colt.matrix.DoubleMatrix2D}. 
  This is the interface to operate on.</p>
<p>Class naming for concrete instantiable classes follows the schema <tt>&lt;Property&gt;&lt;ValueType&gt;Matrix&lt;Rank&gt;D</tt>. 
  For example, we have a {@link cern.colt.matrix.impl.DenseDoubleMatrix2D}, a 
  {@link cern.colt.matrix.impl.SparseDoubleMatrix2D}, a {@link cern.colt.matrix.impl.DenseIntMatrix3D}, 
  and so on. All concrete instantiable classes are separated into an extra package, 
  {@link cern.colt.matrix.impl}, to clearly distinguish between interfaces and 
  implementations.</p>
<p>{@link cern.colt.matrix.DoubleMatrix2D} in turn is derived from an abstract 
  base class tying together all 2-dimensional matrices regardless of value type, 
  {@link cern.colt.matrix.impl.AbstractMatrix2D}, which finally is rooted in grandmother 
  {@link cern.colt.matrix.impl.AbstractMatrix}.</p>
<p>The abstract base classes provide skeleton implementations for all but few 
  methods. Experimental data layouts can easily be implemented and inherit a rich 
  set of functionality. For example, to implement a fully functional 2-d or 3-d 
  matrix, only 6 abstract methods need to be overridden: <tt>getQuick, setQuick, 
  like, like1D, viewSelectionLike</tt>.</p>
<h4>Method Naming</h4>
<p>In order to improve browsing and better keep an overview, the namespace of 
  logically related operations is localized: Methods getting and setting individual 
  cell values are named <tt>get</tt> and <tt>set</tt>. Methods constructing views 
  are named <tt>viewXXX</tt> (e.g. <tt>viewPart</tt>). Copying/assignment methods 
  are named <tt>copy</tt> and <tt>assignXXX</tt>. Mathematical operations are 
  named <tt>zXXX</tt> (e.g. <tt>zMult</tt>). Generic aggregation operations are 
  named <tt>aggregateXXX</tt>.</p>
<h4>Convenience Methods</h4>
<p>To keep interfaces lean and manageable, we tried to avoid littering them with 
  convenience methods obfuscating more fundamental concepts. Convenience operations 
  expressible in one to three lines of code are omitted. For example, all operations 
  modifying cell values modify the receiver (<tt>this</tt>) itself. There are 
  no methods to fill results into empty result matrices. Use idioms like <tt>result 
  = matrix.copy().mult(5)</tt> to achieve the same functionality. Some convenience 
  methods are provided in the factory classes as well as in external packages 
  like {@link cern.colt.matrix.doublealgo}.</p>
<p><a href="#Overview">Back</a> to Overview 
<h2><a name="Performance"></a>9. Performance</h2>
<p>The following statements apply to all currently implemented features (i.e. 
  dense and sparse matrices including all view kinds), except where indicated.</p>
<p> Constant factors are kept as small as possible.Views are constructed in guaranteed 
  <tt>O(1)</tt>, i.e. constant time, except for selection views and sort views: 
  Selection views take time linear in the number of indexes, sort views take <tt>O(N*logN)</tt> 
  on average. Getting/setting a cell value takes <i>guaranteed </i>constant time 
  for <font color="#CC0000">dense</font> matrices (and all their views), while 
  it takes <i>expected</i> constant time for sparse hash matrices (and all their 
  views). More specifically, on <font color="#CC0000">sparse hash</font> matrices, 
  these operations can, although highly improbable, degenerate to time linear 
  in the number of non-zero cells. This is because of the nature of hashing: Average 
  case behaviour is extremely good, worst case behaviour is bad. </p>
<p><font color="#CE0000">Sparse row compressed</font> matrices have the following 
  characteristics: Getting a cell value takes time<tt> O(log nzr)</tt> where <tt>nzr</tt> 
  is the number of non-zeros of the touched row. This is usually quick, because 
  typically there are only few nonzeros per row. So, in practice, get has <i>expected</i> 
  constant time. Setting a cell value takes <i> </i>worst-case time <tt>O(nz)</tt> 
  where <tt>nzr</tt> is the total number of non-zeros in the matrix. This can 
  be extremely slow, but if you traverse coordinates properly, each write is done 
  much quicker. For how to do this and other tips, see the <a href="doc-files/performanceNotes.html">performance 
  notes</a>. <img src="../doc-files/new.gif" width="32" height="22" align="middle"> 
</p>
<p></p>
<p>Some preliminary benchmarks can be found in the <a href="doc-files/PerformanceLogFrame.html">performance 
  log</a>.</p>
<p>All matrices use strided 32-bit integer arithmetic for linear cell addressing, 
  similar to Fortran. The chosen cell addressing implementation is the key feature 
  enabling the easy implementation and good performance of advanced views.</p>
<p>All methods are bounds checking, except for trusting variants of <tt>get</tt> 
  and <tt>set</tt> called <tt>getQuick</tt> and <tt>setQuick</tt> which should 
  and are used in expensive (often cubic) loops where it is dramatically cheaper 
  to check bounds before entering the loop, not in the loop. Fundamentally time 
  critical methods of dense matrices override default implementations such that 
  iteration eliminates function calls, minimizes cell addressing overhead and 
  gets pipelined. Some operations use processor cache oriented optimization techniques 
  such as memory layout aware iteration, blocking of slow changing operands followed 
  by logical optimizations such as sparsity detection.</p>
<p>In order to eliminate expensive call chains, views directly point to the data 
  without indirection, no matter how deeply nested they are. In particular they 
  are not implemented with delegation. In fact they are not nested at all, even 
  if they logically appear like that. There is largely no distinction between 
  views and non-views. Note that this is not true for row-compressed matrices; 
  their views are wrappers and do use delegation (aka call chains). <img src="../doc-files/new.gif" width="32" height="22" align="top"></p>
<p>Although view objects occupy only a couple of bytes, generating temporary views 
  at very high frequency can lead to heavy garbage collection. </p>
<p>To keep the overhead minimal, copying operations are highly optimized. They 
  sometimes boil down to <tt>System.arraycopy</tt> (which is nothing else than 
  a byte-aligned C <tt>memmove</tt>). Also note that memory access patterns (cache 
  locality) of self-modifying matrix operations are better than for result matrix 
  modifying operations.</p>
<p><a href="#Overview">Back</a> to Overview 
<h2></h2>
<h2><a name="Notes"></a>10. Notes </h2>
<h2></h2>
<p>Matrices are not dynamically resizable; it is impossible to physically insert 
  or remove cells. Some logical cell removal and insertion can be achieved by 
  means of views. To achieve physical cell removal or insertion, a new matrix 
  with the needed shape must be constructed and cells copied. Note, however, that 
  there are convenience methods to do many kind of resizing operations.</p>
<p>Another current limitation is the inability to address more than 2<sup>31</sup> 
  cells. This can be a problem for very large sparse matrices. 64-bit addressing 
  is possible, but unlikely to be implemented unless there is serious demand.</p>
<p><a href="#Overview">Back</a> to Overview</p>
</BODY>
</HTML>